Trường hợp

Một vấn đề tính toán có thể xem là một tập vô hạn các trường hợp cùng với lời giải cho mỗi trường hợp. Không nên nhầm lẫn giữa dữ liệu vào cho mỗi vấn đề tính toán, còn gọi là một trường hợp, và bản thân vấn đề. Trong lý thuyết độ phức tạp tính toán, một vấn đề là một câu hỏi trừu tượng cần giải quyết. Một trường hợp là một trường hợp cụ thể của câu hỏi trừu tượng đó. Để rõ hơn, ta xem xét vấn đề kiểm tra tính nguyên tố. Một trường hợp là một số nguyên (ví dụ như 15) và lời giải là "có" nếu như số đó là nguyên tố và "không" nếu nó không là nguyên tố (trong trường hợp này, lời giải là "không").

Biểu diễn trường hợp

Khi xem xét các vấn đề tính toán, một trường hợp là một xâu ký tự trong một bảng chữ cái nhất định. Bảng chữ cái thường dùng là bảng chữ cái nhị phân (gồm 2 ký tự 0 và 1). Cũng như trong máy tính trên thực tế, các đối tượng toán học cần phải được mã hóa hợp lý dưới dạng các dãy bit. Ví dụ như một số nguyên cần phải được biểu diễn dưới dạng nhị phân, đồ thị có thể được biểu diễn dưới dạng ma trận kề, hoặc mã hóa danh sách kề dưới dạng nhị phân.

Mặc dù một số chứng minh của các định lý trong lý thuyết độ phức tạp tính toán giả sử một mã hóa nhất định của dữ liệu vào, người ta thường cố gắng giữ cho các lập luận đủ trừu tượng để không phụ thuộc vào cách mã hóa. Điều này có thể đạt được bằng cách đảm bảo có thể được chuyển từ cách mã hóa này sang cách mã hóa khác một cách hiệu quả.

Bài toán quyết định dưới dạng ngôn ngữ hình thức

Bài toán quyết định là một trong những đối tượng trọng tâm nghiên cứu của lý thuyết độ phức tạp tính toán. Một bài toán quyết định là một trường hợp đặc biệt của bài toán tính toán, với câu trả lời là có hoặc không, hay nói cách khác là 0 hoặc 1. Một bài toán quyết định có thể được xem là một ngôn ngữ hình thức, trong đó các xâu ký tự thành viên của ngôn ngữ là các những trường hợp có câu trả lời là có, các xâu ký tự không là thành viên là những trường hợp có câu trả lời là không. Mục tiêu của bài toán là sử dụng một thuật toán để quyết định xem một xâu cho trước có là thành viên của ngôn ngữ hình thức đang xem xét hay không. Nếu thuật toán quyết định là có, thì ta nói thuật toán chấp nhận xâu dữ liệu vào, nếu không thì ta nói thuật toán từ chối xâu dữ liệu vào.

Một ví dụ của bài toán quyết định là như sau. Dữ liệu vào là một đồ thị bất kì. Bài toán yêu cầu quyết định xem đồ thị có liên thông hay không. Ngôn ngữ hình thức tương ứng cho bài toán này là tập tất cả các đồ thị liên thông. Dĩ nhiên để định nghĩa chặt chẽ bài toán, cần phải quyết định xem đồ thị được mã hóa như thế nào dưới dạng xâu nhị phân.

Bài toán hàm

Một bài toán hàm là một bài toán tính toán trong đó mỗi dữ liệu vào cho đúng một kết quả, nhưng kết quả đó phức tạp hơn kết quả của bài toán quyết định, nghĩa là nó không chỉ là có hay không. Ví dụ như bài toán người bán hàng, và bài toán phân tích ra thừa số nguyên tố.

Thoạt nhìn có vẻ khái niệm bài toán hàm là rộng hơn khái niệm bài toán tính toán. Tuy nhiên, điều này không hẳn là đúng do các bài toán hàm có thể được viết lại dưới dạng bài toán quyết định. Ví dụ như bài toán nhân hai số nguyên có thể được biểu diễn dưới dạng tập hợp các bộ ba (a, b, c) sao cho a × b < c. Quyết định xem liệu một bộ ba cho trước có phải là thành viên của tập hợp đó hay không tương ứng với việc nhân hai số.

Kích thước của trường hợp

Để đánh giá độ khó của một bài toán tính toán, một thước đo phổ biến là lượng thời gian thuật toán tốt nhất cần dùng để giải nó. Tuy nhiên, thời gian cần thiết nói chung phụ thuộc vào từng trường hợp cụ thể. Trường hợp lớn hơn thường đòi hỏi nhiều thời gian hơn. Do đó thời gian cần thiết để giải quyết bài toán (hoặc bộ nhớ, hay bất kì một thông số độ phức tạp nào) là một hàm số của kích thước trường hợp. Kích thước thường được đo bằng kích thước dữ liệu vào với đơn vị bit. Lý thuyết độ phức tạp quan tâm đến hành vi của thuật toán khi kích thước dữ liệu vào tăng lên. Ví dụ như trong bài toán kiểm tra xem một đồ thị có liên thông hay không, thời gian cần thiết để kiểm tra một đồ thị kích thước 2n là bao nhiêu so với thời gian để kiểm tra đồ thị kích thước n?

Khi kích thước dữ liệu vào là n, thời gian có thể được biểu diễn dưới dạng một hàm số của n. Do thời gian cần thiết cho các trường hợp cùng kích thước có thể khác nhau, thời gian trong trường hợp xấu nhất T(n) được định nghĩa là lượng thời gian lớn nhất trong tất cả các trường hợp có kích thước n. Nếu T(n) là đa thức của n, thì ta nói thuật toán chạy thời gian đa thức.